//#define _CRT_SECURE_NO_WARNINGS 1
//#include<iostream>
//#include"test.h"
//using namespace std;
//void queueindit(Queue* pe,int k)
//{
//	pe->a = (int*)malloc(sizeof(int) * k);
//	if (pe->a == NULL)
//	{
//		perror("malloc::false");
//		return;
//	}
//	pe->front = pe->rear = 0;
//}
//bool queuepush(Queue* pe,int x,int k)
//{
//	assert(pe);
//	if ((pe->rear+1) % k == pe->front)
//	{
//		return false;
//	}
//	pe->a[(pe->rear) % x] = k;
//	pe->rear++;
//	return true;
//}
//int queuepop(Queue* pe)
//{
//	assert(pe);
//	if (isempty(pe))
//	{
//		return -1;
//	}
//	return pe->a[pe->front];
//}
//bool isempty(Queue* pe)
//{
//	if (pe->front == pe->rear)
//	{
//		return true;
//	}
//	else
//	{
//		return false;
//	}
//}
//bool isfull(Queue* pe,int k)
//{
//	assert(pe);
//	if ((pe->rear) % k == pe->front)
//	{
//		return true;
//	}
//	else
//	{
//		return false;
//	}
//}
//int front(Queue* pe,int k)
//{
//	assert(pe);
//	if (isempty(pe))
//	{
//		return -1;
//	}
//	else
//	{
//		return pe->a[pe->front];
//	}
//}


//#include"test.h"
//using namespace std;
//void Heapindit(Heap* hp)
//{
//	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * 10);
//	if (hp->a == NULL)
//	{
//		perror("malloc::false");
//		return;
//	}
//	hp->_size = 0;
//	hp->_capacity = 10;
//}
//void HeapPush(Heap* hp, HPDataType x)
//{
//	if (hp->_size == hp->_capacity)
//	{
//		HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * hp->_capacity * 10);
//		hp->_capacity *= 10;
//	}
//	hp->a[hp->_size] = x;
//	ADDjustup(hp, hp->_size);
//	hp->_size++;
//}
//void ADDjustup(Heap* hp, int child)
//{
//
//	while (child > 0)
//	{
//		int parent = (child - 1) / 2;
//		if (hp->a[child] > hp->a[parent])
//		{
//			Swap(&hp->a[child], &hp->a[parent]);
//			child = parent;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//
//void Swap(HPDataType* a1, HPDataType* a2)
//{
//	int t = *a1;
//	*a1 = *a2;
//	*a2 = t;
//}
//void HeapDestory(Heap* hp)
//{
//	assert(hp);
//	free(hp->a);
//	hp->a = NULL;
//}
//void HeapPop(Heap* hp)
//{
//	assert(hp->_size);
//	assert(hp);
//	Swap(&hp->a[0], &hp->a[hp->_size - 1]);
//	hp->_size--;
//	ADDjustdown(hp, 0);
//}
//void ADDjustdown(Heap* hp, int parent)
//{
//	while (parent < hp->_size)
//	{
//		int child = parent * 2;
//		if (hp->a[child] < hp->a[child + 1])
//		{
//			child++;
//		}
//		if (hp->a[child] > hp->a[parent])
//		{
//			Swap(&hp->a[child], &hp->a[parent]);
//			parent = child;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//HPDataType HeapTop(Heap* hp)
//{
//	assert(hp);
//	return hp->a[0];
//}
//int HeapSize(Heap* hp)
//{
//	assert(hp);
//	return hp->_size;
//}
//int HeapEmpty(Heap* hp)
//{
//	assert(hp);
//	return hp->_size;
//}
//void PrintTopK(Heap*hp, int n, int k)
//{
//	for (int i = n / 2; i >= 0; i--)
//	{
//		ADDjustdown(hp, i);
//	}
//	while (k--)
//	{
//		cout << hp->a[0]<<' ';
//		Swap(&hp->a[0], &hp->a[hp->_size - 1]);
//		hp->_size--;
//		ADDjustdown(hp, 0);
//	}
//}


//#include"test.h"
//MyCircularQueue* myCircularQueueCreate(int k)
//{
//	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//	assert(obj);
//	obj->a = (int*)malloc(sizeof(int) * (k + 1));
//	obj->front = 0;
//	obj->rear = 0;
//	obj->k = k;
//	return obj;
//}
//int myCircularQueueFront(MyCircularQueue* obj)
//{
//	if (myCircularQueueIsEmpty(obj))
//	{
//		return -1;
//	}
//	return obj->a[obj->front];
//}
//int myCircularQueueRear(MyCircularQueue* obj)
//{
//	if (myCircularQueueIsEmpty(obj))
//	{
//		return -1;
//	}
//	return obj->a[obj->rear-1];
//}
//bool myCircularQueueIsEmpty(MyCircularQueue* obj)
//{
//	return obj->rear%obj->k == obj->front;
//}
//
//bool myCircularQueueIsFull(MyCircularQueue* obj)
//{
//	return (obj->rear+1)%(obj->k+1)==obj->front;
//}
//void myCircularQueueFree(MyCircularQueue* obj)
//{
//	free(obj->a);
//	obj->a = NULL;
//}
//bool myCircularQueueDeQueue(MyCircularQueue* obj)
//{
//	if (myCircularQueueIsEmpty(obj))
//	{
//		return false;
//	}
//	else
//	{
//		obj->front++;
//		obj->front %= obj->k;
//		return true;
//	}
//}
//bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
//{
//	assert(obj);
//	if (myCircularQueueIsFull(obj))
//	{
//		return false;
//	}
//	if (obj->rear ==obj->k)
//	{
//		obj->rear = 0;
//	}
//	obj->a[obj->rear++] = value;
//	return true;
//}



//#include<assert.h>
//#include<iostream>
//using namespace std;
//typedef struct tire {
//	int n;
//	struct tire* left;
//	struct tire* right;
//}tire;
//void mid(tire*l1)
//{
//	if (l1 == NULL)
//	{
//		cout << "NULL" << "->";
//		return;
//	}
//	else
//	{
//		mid(l1->left);
//		cout <<l1->n<<"->";
//		mid(l1->right);
//	}
//}
//int main()
//{
//	tire* l1 = (tire*)malloc(sizeof(tire));
//	tire* l2 = (tire*)malloc(sizeof(tire));
//	tire* l3 = (tire*)malloc(sizeof(tire));
//	tire* l4 = (tire*)malloc(sizeof(tire));
//	tire* l5 = (tire*)malloc(sizeof(tire));
//	tire* l6 = (tire*)malloc(sizeof(tire));
//	l1->n = 1;
//	l1->left = l2;
//	l1->right = l3;
//	l2->n = 2;
//	l3->n = 3;
//	l2->left = l4;
//	l2->right = l5;
//	l3->left = l6;
//	l3->right = NULL;
//	l4->n = 4;
//	l5->n = 5;
//	l6->n = 6;
//	l4->left = l4->right = NULL;
//	l5->left = l5->right = NULL;
//	l6->left = l6->right = NULL;
//	mid(l1);
//	return 0;
//}



//#include<iostream>
//using namespace std;
//int main()
//{
//	
//
//
//	return 0;
//}



//#include<iostream>
//using namespace std;
//typedef struct tree {
//	int a;
//	struct tree* left;
//	struct tree* right;
//}tree;
//void prevorder(tree* root)
//{
//	if (root == NULL)
//	{
//		printf("NULL->");
//		return;
//	}
//		printf("%d->", root->a);
//		prevorder(root->left);
//		prevorder(root->right);
//}
//int main()
//{
//	tree* tree1 = (tree*)malloc(sizeof(tree));
//	tree* tree2 = (tree*)malloc(sizeof(tree));
//	tree* tree3 = (tree*)malloc(sizeof(tree));
//	tree* tree4 = (tree*)malloc(sizeof(tree));
//	tree* tree5 = (tree*)malloc(sizeof(tree));
//	tree* tree6 = (tree*)malloc(sizeof(tree));
//	tree* tree7 = (tree*)malloc(sizeof(tree));
//	tree* tree8 = (tree*)malloc(sizeof(tree));
//	tree1->a = 1;
//	tree2->a = 2;
//	tree3->a = 3;
//	tree4->a = 4;
//	tree5->a = 5;
//	tree6->a = 6;
//	tree7->a = 7;
//	tree8->a = 8;
//	tree1->left = tree2;
//	tree1->right = tree3;
//	tree2->left = tree4;
//	tree2->right = tree5;
//	tree3->left = tree6;
//	tree3->right = tree7;
//	tree7->left = tree8;
//	tree8->left = tree8->right = NULL;
//	tree7->right = NULL;
//	tree4->left = tree4->right = NULL;
//	tree5->left = tree5->right = NULL;
//	tree6->left = tree6->right = NULL;
//	prevorder(tree1);
//	return 0;
//}

#include<assert.h>
#include"test.h"
void BinaryTreePrevOrder(BTNode* root)
{
	//assert(root);
	if (root == NULL)
	{
		printf("NULL->");
		return;
	}
	printf("%c->", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}


int BinaryTreeLeafSize(BTNode* root)
{
	int left = 0;
	int right = 0;
	if (root == NULL)
	{
		return 0;
	}
	left=BinaryTreeLeafSize(root->_left);
	if ((!root->_left) && (!root->_right))
	{
		return left + 1;
	}
	right=BinaryTreeLeafSize(root->_right);
	if ((!root->_left) && (!root->_right))
	{
		return right + 1;
	}
	return left + right;
}



int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	int left = BinaryTreeLevelKSize(root->_left, k - 1);
	int right= BinaryTreeLevelKSize(root->_right, k - 1);
	return left + right;
}

int TreeHigh(BTNode* root)
{
	if (root == NULL)
	{
		return 1;
	}
	int lefthigh = TreeHigh(root->_left);
	if (root->_left != NULL)
	{
		return lefthigh + 1;
	}
	int righthigh = TreeHigh(root->_right);
	if (root->_right != NULL)
	{
		return righthigh + 1;
	}
	return max(lefthigh, righthigh);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		cout << "NULL->";
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	cout << root->_data << "->";
}


void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		cout << "NULL->";
		return;
	}
	BinaryTreeInOrder(root->_left);
	cout << root->_data << "->";
	BinaryTreeInOrder(root->_right);
}


BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* left = BinaryTreeFind(root->_left, x);
	BTNode* right = BinaryTreeFind(root->_right, x);
	if (right)
	{
		return right;
	}
	if (left)
	{
		return left;
	}
	return NULL;
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = BinaryTreeSize(root->_left);
	if (root != NULL)
	{
		return left + 1;
	}
	int right = BinaryTreeSize(root->_right);
	if (root != NULL)
	{
		return right + 1;
	}
	return left + right;
}

void BinaryTreeDestory(BTNode** root);



















